/**
 * 插入排序
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
  // 已排序区间 [0, i) ，未排序区间 [i , len)
  console.time("插入排序耗时");
  // 将 nums[i] 插入到区间 [0, i) 使之成为有序数组
  for (let i = 1; i < nums.length; i++) {
    // 从右往左遍历有序序列
    for (let j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
      // 只要nums[j]比前一个元素nums[j-1]小，就交换这两个元素
      let temp = nums[j];
      nums[j] = nums[j - 1];
      nums[j - 1] = temp;
    }
  }
  console.timeEnd("插入排序耗时");
  return nums;
};

let arr = sortArray([6, 9, 0, 4, 8, 3, 2, 7, 1, 5]);
console.log(arr);
